/*
 * @lc app=leetcode.cn id=1818 lang=typescript
 *
 * [1818] 绝对差值和
 */

// @lc code=start
function minAbsoluteSumDiff(nums1: number[], nums2: number[]): number {
  const m = nums1.length;
  const mod = 10 ** 9 + 7;
  // 二分查找使用
  const temp = [...nums1];
  temp.sort((a, b) => a - b);
  // 保存最大绝对差值和
  let sum = 0;
  // 保存元素最大的差值
  let max = 0;
  for (let i = 0; i < m; i++) {
    const diff = Math.abs(nums1[i] - nums2[i]);
    sum = (sum + diff) % mod;
    let idx = binarySearch(temp, nums2[i]);
    // 最接近nums2[i]的元素可能是大于它的，也可能是小于它的
    // 所以计算了2次，取较大差值
    if (idx < m) {
      max = Math.max(max, diff - (temp[idx] - nums2[i]));
    }
    if (idx > 0) {
      max = Math.max(max, diff - (nums2[i] - temp[idx - 1]));
    }
  }

  return (sum - max + mod) % mod;

  function binarySearch(temp: number[], target: number): number {
    // 找到第一个大于等于target的下标
    let l = 0;
    let r = temp.length - 1;
    if (temp[r] < target) return r + 1;
    let mid: number;
    while (l < r) {
      mid = l + ((r - l) >> 1);
      if (temp[mid] < target) l = mid + 1;
      else r = mid;
    }
    return l;
  }
}
// @lc code=end
